//给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：root = [4,2,7,1,3,6,9]
//输出：[4,7,2,9,6,3,1]
// 
//
// 示例 2： 
//
// 
//
// 
//输入：root = [2,1,3]
//输出：[2,3,1]
// 
//
// 示例 3： 
//
// 
//输入：root = []
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 树中节点数目范围在 [0, 100] 内 
// -100 <= Node.val <= 100 
// 
//
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 1654 👎 0


package LeetCode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author ldltd
 * @date 2023-08-16 23:00:53
 * @description 226.翻转二叉树
 */
public class InvertBinaryTree{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new InvertBinaryTree().new Solution();

	 }

//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

 // Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
    /*递归实现，当为null返回   时间on,空间o h，h为高度，*/
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode t = root.left;
        root.left = root.right;
        root.right = t;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

/*时间空间On bfs*/
    public TreeNode invertTree1(TreeNode root) {
        if (root == null) {
            return root;
        }
        //把树逐层放入队列。再迭代处理
        Queue<TreeNode> q= new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()){
            TreeNode node = q.poll();
            TreeNode t = node.left;
            node.left=node.right;
            node.right=t;
            //如果当前节点左子树不为空，加入队列处理
            if(node.left!=null) q.offer(node.left);
            if(node.right!=null) q.offer(node.right);
        }
        return root;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
